package sort;

import tree.TreeNode;

public class QuickSort {

    public static void main(String[] args) {
        QuickSort sorter = new QuickSort();

        // 测试用例1: 原始测试用例
        System.out.println("测试用例1:");
        int[] arr1 = {1, 5, 2, 4, 3};
        sorter.quickSort(arr1, 0, arr1.length - 1);
        printArray(arr1);

        // 测试用例2: 已排序数组
        System.out.println("\n测试用例2 (已排序数组):");
        int[] arr2 = {1, 2, 3, 4, 5};
        sorter.quickSort(arr2, 0, arr2.length - 1);
        printArray(arr2);

        // 测试用例3: 逆序数组
        System.out.println("\n测试用例3 (逆序数组):");
        int[] arr3 = {5, 4, 3, 2, 1};
        sorter.quickSort(arr3, 0, arr3.length - 1);
        printArray(arr3);

        // 测试用例4: 包含重复元素
        System.out.println("\n测试用例4 (包含重复元素):");
        int[] arr4 = {3, 1, 4, 1, 5, 9, 2, 4, 5};
        sorter.quickSort(arr4, 0, arr4.length - 1);
        printArray(arr4);

        // 测试用例5: 单个元素
        System.out.println("\n测试用例5 (单个元素):");
        int[] arr5 = {42};
        sorter.quickSort(arr5, 0, arr5.length - 1);
        printArray(arr5);

        // 测试用例6: 空数组
        System.out.println("\n测试用例6 (空数组):");
        int[] arr6 = {};
        sorter.quickSort(arr6, 0, arr6.length - 1);
        printArray(arr6);
    }

    // 辅助方法：打印数组
    private static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }


    public void quickSort(int[] arr, int start, int end){
        if(start >= end){
            return;
        }
        int temp = arr[(start + end) / 2];
        int left = start;
        int right = end;
        while (left < right){
            if(arr[right] > temp){
                while (arr[right] > temp && left < right){
                    right --;
                }
            }
            if(arr[left] < temp){
                while (arr[left] < temp && left < right){
                    left++;
                }
            }
            if(arr[left] >= temp && arr[right] <= temp){
                swap(arr, left, right);
            }
            right--;
        }
      //  arr[left] = temp;
        quickSort(arr,0,left);
        quickSort(arr,left + 1,end);
    }

    private void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

}
